1. Field of the Invention
This invention relates to an improvement in a programming support system and programming support method. More specifically, this invention relates to a programming support system and programming support method that make it easy to develop highly-reliable concurrent programs.
2. Description of the Prior Art
A recent advance in the semi-conductor integrated circuit technology makes possible a complicated processor and a large memory compact and low-cost. This technology makes it possible to build a concurrent system or distributed system composed of many processors. This type of hardware requires special programs such as concurrent programs or distributed programs (hereafter called concurrent program (CP)).
When concurrent programs run, a plurality of processes run simultaneously and concurrently. Typically, a plurality of programs run concurrently on a parallel computer having a plurality of CPUs. A program which runs on a single CPU sequentially but has a plurality of processes running concurrently in a multi-task system is also called a concurrent program. A system featuring physical or logical concurrency is called a concurrent system, where, in general, concurrent programs run. Today, it becomes important not only to develop an efficient concurrency algorithm but also to develop a method for developing concurrent programs efficiently.
Program development efficiency depends largely on finding and correcting bugs in a program, one of program development processes called a test/debug process. Especially, in developing concurrent programs, there are problems specific to concurrent program development which are not found in developing sequential programs. One of these problems is that the processes of a concurrent program do not synchronize with each other and, as a result, the whole concurrent program does not behave correctly. This problem, generated because of concurrent program characteristics, is usually called "nondeterminism".
There are three types of nondeterminism: intended, harmful, and harmless. A intended nondeterminism is the one intentionally introduced by the (program) designer. This nondeterminism, which allows the program to react properly to nondeterminate external stimuli, makes the processes flexible, re-usable, and expandable.
On the other hand, a harmful nondeterminism, which is unintentionally introduced by the designer, sometimes causes program function errors. Human process of thinking, which is sequential, sometimes does not cover all the situations which will be produced by a plurality of processes in concurrent programs. For this reason, some situations not expected by the designer may be generated during execution of concurrent programs.
A harmless nondeterminism affects execution efficiency but does not affect the final result.
The following describes a harmful nondeterminism. Consider the concurrent program shown in FIG. 33. In FIG. 33(a), process P1 (init) initializes the shared memory M, process P2 (read) reads data from the shared memory M, and process P3 (write) writes data into the shared memory M. When these processes run in a concurrent processing system, each on a separate processor, there are six combinations as shown in FIG. 33(b). Because the system operation usually begins with initialization and the correct result is obtained only when the program runs in the sequence of process P1 (init).fwdarw.P2 (read).fwdarw.P3 (write) or P1 (init).fwdarw.P3 (write).fwdarw.P2 (read), the remaining four combinations (for example, P2.fwdarw.P3.fwdarw.P1), which do not begin with initialization, do not produce the correct result.
The above description indicates that nondeterminism associated with process behavior causes a concurrent program to produce a result depending upon the system status and so on during execution of the program. This means that, as long as nondeterminate problems remain unsolved, concurrent programs, though successfully tested, do no always run correctly.
In most cases, it is more difficult to find bugs associated with nondeterminism than to find bugs in a sequential program. The reason is as follows. The programmer can pass control to all the paths when debugging and testing sequential programs, while the programmer must pass control to all the combinations of paths when debugging and testing concurrent programs (that is, not only all the paths in each process but also all the combinations of process behaviors must be considered). Although it is relatively easy to examine all the combinations of process behaviors in such a simple case described above, a huge number of combinations must be examined in practical program development. In practice, it is impossible to trace all the combinations.